// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-04-19 00:01
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.TREE.segTree;

import java.util.Set;
import java.util.TreeMap;

class MyCalendarThree {
    /*
        开点线段树 -> 插入区间节点的时候直接插入到叶子节点
     */

    class Node {
        int value;
        int start, end;
        Node left, right;

        public Node(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    private final int N = (int) 1e+9;
    // 可能会出现OOM
    Node root;


    public Node buildTree(int start, int end) {
        Node node = new Node(start, end);
        if (start == end) {
            return node;
        }
        int mid = start + end >> 1;
        node.left = buildTree(start, mid);
        node.right = buildTree(mid + 1, end);
        return node;
    }


    public MyCalendarThree() {
        root = new Node(0, N);
    }

    public int book(int start, int end) {
        return book(root, start, end);
    }

    /*
        线段树的查询插入方法
     */
    private int book(Node root, int start, int end) {



        return 0;
    }


    public static void main(String[] args) {
        MyCalendarThree mct = new MyCalendarThree();
//        System.out.println(mct.book(10, 20));
//        System.out.println(mct.book(50, 60));
//        System.out.println(mct.book(10, 40));
//        System.out.println(mct.book(5, 15));
//        System.out.println(mct.book(5, 10));
//        System.out.println(mct.book(25, 55));
    }
}

/**
 * Your MyCalendarThree object will be instantiated and called as such:
 * MyCalendarThree obj = new MyCalendarThree();
 * int param_1 = obj.book(start,end);
 */

//
//{
//    /*
//        使用动态开点的方法构建线段树
//        // 在树的创建过程中，如果不使用返回值为Node类型的构建树方法，因为传入的树节点为空，所以创建的树只是临时的
//        // 通过使用数组进行改进，因为book的次数最多为400次，所有线段树的线段节点最大为400 * 2
//        // 查询的结果不是区间的重合次数而是预定的次数
//     */
//public final int N = 400;
//        Node[] node = new Node[N * 3];
//
//class Node {
//    int start, end;
//    int value;
//
//    public Node(int start, int end) {
//        this.start = start;
//        this.end = end;
//    }
//}
//
//
//    public MyCalendarThree() {
//
//    }
//
//    public int book(int start, int end) {
//        return book(1, start, end);
//    }
//
//    private int book(int index, int start, int end) {
//        Node root = node[index];
//        if (root == null) {
//            node[index] = new Node(start, end);
//            node[index].value++;
//            return node[index].value;
//        }
//        /*-----当前节点表示的范围在查询的范围内-----*/
//        if (root.start >= start && root.end <= end) {
//            root.value++;
//            book(index << 1, start, root.start);
//            book(index << 1 | 1, root.end, end);
//            return root.value;
//        }
//        /*   int mid = root.start + root.end >> 1;
//         *//*-----查询区间单独出现在当前节点的左边或者右边-----*//*
//        if (mid >= end) {
//            return book(root.left, start, end);
//        } else if (mid < start) {
//            return book(root.right, start, end);
//        }*/
//        /*-----查询的区域和当前节点表示的范围没有重合区域----*/
//        if (start >= root.end) {
//            return book(index << 1 | 1, start, end);
//        }
//        if (end <= root.start) {
//            return book(index << 1, start, end);
//        }
//
//        /*-----查询区域和当前节点的左右子节点表示的区间有部分重合-----*/
//        if (end > root.end) {
//            root.value++;
//            return root.value + book(index << 1 | 1, root.end, end) - 1;
//        }
//        if (start < root.start) {
//            root.value++;
//            return root.value + book(index << 1, start, root.start) - 1;
//        }
//        return 0;
//        // return Math.max(book(root.left, start, mid), book(root.right, mid + 1, end));
//    }


//}